A cache is a block of memory for temporary storage of data likely to be used again. Caches are used in a number of applications where frequently accessed data can be stored for rapid access including, but not limited to, central processing units (CPU), hard drives, web browsers, content delivery networks and web servers. The cache is made up of a pool of entries, each entry having a piece of data which is a copy of data stored in a backup data store. Each entry also includes a key which specifically identifies the data. When a client wishes to access the data, it first checks the cache and if the entry can be found with a key matching that of the desired data, the cache data in the entry is used instead. This is referred to as a cache hit. A success in the use of the cache can be measured by a hit rate or hit ratio of the cache. The hit ratio is the ratio of accesses satisfied by cache to the total number of accesses. When the cache is consulted and not found to contain a piece of data with the desired key, this is known as a cache miss. Typically, caches have limited storage. Caches may therefore eject some entries in order to make room for others. A number of different heuristics are utilized to determine whether to eject or include an entry in the cache. These heuristics are generally referred to as replacement policies.
Caches may also be divided into levels. A level one (L1) cache is typically a higher performance cache than a level two (L2) cache. Typically, the L2 cache is a secondary staging area that feeds objects to the L1 cache. Other levels of cache memory are possible.
Memory compression has been utilized in operating system memory management and virtual memory systems to create uncompressed and compressed memory pages in order to improve the performance of applications running in computers. Compressed caching is a technique that uses parts of the available cache to hold data entries in a compressed form, effectively adding a new level cache to the system. The sizes of respective uncompressed and compressed caches have been adapted to applications in virtual memory systems.